#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
using namespace std;
#include<time.h>

void sortColors(vector<int>& nums) {
    int left = -1;
    int right = nums.size();

    int i = 0;
    while (i < right)
    {
        if (nums[i] == 0)
        {
            left++;
            swap(nums[left], nums[i]);
            i++;
        }
        else if (nums[i] == 1)
        {
            i++;
        }
        else
        {
            right--;
            swap(nums[right], nums[i]);
        }
    }
}

void my_sort(vector<int>& nums, int begin, int end)
{
    if (begin >= end)
        return;
    int left = begin - 1, right = end + 1;
    int mid = rand() % (end - begin + 1) + begin;

    int key = nums[mid];
    int i = begin;
    while (i < right)
    {
        if (nums[i] < key)
        {
            swap(nums[++left], nums[i++]);
        }
        else if (nums[i] == key)
        {
            i++;
        }
        else
        {
            swap(nums[--right], nums[i]);
        }
    }
    my_sort(nums, begin, left);
    my_sort(nums, right, end);
}

vector<int> sortArray(vector<int>& nums) {
    srand(time(NULL));
    int n = nums.size();
    int begin = 0, end = n - 1;
    my_sort(nums, begin, end);
    return nums;
}

int findKthLargest(vector<int>& nums, int k) {
    srand(time(NULL));
    return qsort(nums, 0, nums.size() - 1, k);
}

int qsort(vector<int>& nums, int begin, int end, int k)
{
    if (begin == end)
        return nums[begin];

    int left = begin - 1, right = end + 1, i = begin;
    int key = nums[rand() % (end - begin) + begin];
    while (i < right)
    {
        if (nums[i] < key)
        {
            ++left;
            swap(nums[left], nums[i]);
            i++;
        }
        else if (nums[i] == key)
        {
            i++;
        }
        else
        {
            right--;
            swap(nums[right], nums[i]);
        }
    }

    int c = end - right + 1;
    int b = right - left - 1;

    if (c >= k)
        return qsort(nums, right, end, k);
    else if (b + c >= k)
        return key;
    else
        return qsort(nums, begin, left, k - c - b);
}

vector<int> inventoryManagement(vector<int>& stock, int cnt) {

    srand(time(NULL));
    qsort2(stock, 0, stock.size() - 1, cnt);
    return { stock.begin(),stock.begin() + cnt };
}

void qsort2(vector<int>& nums, int begin, int end, int cnt)
{
    if (begin >= end)
    {
        return;
    }

    int left = begin - 1, right = end + 1, i = begin;
    int key = nums[rand() % (end - begin) + begin];

    while (i < right)
    {
        if (nums[i] < key)
            swap(nums[++left], (nums[i++]));
        else if (nums[i] == key)
            i++;
        else
            swap(nums[--right], nums[i]);
    }

    //[begin,left] [left+1,right-1] [right,end]
    int a = left - begin + 1;
    int b = right - left - 1;
    if (a >= cnt)
        qsort(nums, begin, left, cnt);
    else if (a + b >= cnt)
    {
        return;
    }
    else
        qsort(nums, right, end, cnt - a - b);
}
#include<unordered_map>

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> hash;
    int sum = 0;
    int count = 0;
    hash[0] = 1;
    for (int i = 0; i < nums.size(); i++)
    {
        sum += nums[i];

        if (hash[sum - k])
            count += hash[sum - k];

        hash[sum]++;
    }
    return count;
}